1. Field of the Invention
The present invention relates to authentication of computer users and services in distributed environments. Particularly, the present invention relates to a Remote Pass-phrase Authentication scheme that provides a way to authenticate users and services using a pass-phrase over a computer network without revealing the pass-phrase.
2. Description of the Related Art
The importance of secure communication is increasing as world-wide networks such as the Internet and the World Wide Web (WWW) portion of the Internet expand. As global networks expand through the interconnection of existing networks, users may gain access to an unprecedented number of services. The services, each of which may be maintained by a different provider, give users access to academic, business, consumer, government, etc. information. Service providers are now able to make their services available to an ever-expanding user base.
The ease with which services and users are able to find each other and the convenience associated with on-line transactions is leading to an increase in the number of remote business and related transactions. However, users and services are not always certain who or what is at the other end of a transaction. Therefore, before they engage in business and other transactions, users and services want and need reassurance that each entity with whom they communicate is who or what it purports to be. For example, users will not be willing to make on-line purchases that require them to reveal their credit card numbers unless they are confident that the service with which they are communicating is in fact the service they wanted to access. Commercial and other private entities who provide on-line services may be more reluctant than individuals to conduct business on-line unless they are confident the communication is with the desired individual or service.
Both users and services need reassurance that neither will compromise the integrity of the other nor that confidential information will be revealed unintentionally to third parties while communications are occurring. Security in a global network, however, may be difficult to achieve for several reasons. First, the connections between remote users and services are dynamic. With the use of portable devices, users may change their remote physical locations frequently. The individual networks that comprise the global networks have many entry and exit points. Also, packet switching techniques used in global networks result in numerous dynamic paths that are established between participating entities in order to achieve reliable communication between two parties. Finally, communication is often accomplished via inherently insecure facilities such as the public telephone network and many private communication facilities. Secure communication is difficult to achieve in such distributed environments because security breaches may occur at the remote user""s site, at the service computer site, or along the communication link. Consequently, reliable two-way authentication of users and the services is essential for achieving security in a distributed environment.
Two-way authentication schemes generally involve handshaking techniques so that each party may verify he or she is in communication with the desired party regardless of each party""s location or the types of devices in use. The problem to be solved is one in which a user communicates with a service that wishes to learn and authenticate the user""s identity and vice versa. To clarify the problem, there are three aspects of network security that may be distinguished:
Identification
A user""s identity consists of a user name and a realm name. A realm is a universe of identities. CompuServe Interactive Services (CIS) user IDs and America Online (AOL) screen names are two examples of realms. The combination of user name and realmxe2x80x94typically shown as name@realmxe2x80x94identifies a user. Any given service recognizes some particular set of identities. A realm does not have to be large, though, either in number of users or size of service. For example, a single WWW server may have its own realm of users.
Often, a service recognizes only one realm: CIS recognizes only identities within the CIS realm and AOL recognizes only identities within the AOL realm. But, one can imagine a service that has agreements with both CIS and AOL. The service gives the user a choice of realmsxe2x80x94xe2x80x9cPlease supply a CIS or AOL identity, and prove itxe2x80x9dxe2x80x94and the user chooses a realm in which he or she has an identity. Identification, thus, provides the ability to identify, or to refer to, a user.
Authentication
Authentication provides the ability to prove identity. When asking to do something for which a user""s identity matters, the user may be asked for his or her identityxe2x80x94a user name and realmxe2x80x94and the service requires the user to prove that he is who he says he is. To accomplish this, most services use a secret called a pass-phrase, although it is not necessarily derived from text. Such a secret is sometimes called a secret key, but it is not necessarily used for encryption. In this context, the fundamental problem to be solved is: How can a user prove his pass-phrase without revealing the pass-phrase in the process?
Authorization
Authorization refers to the process of determining whether a given user is allowed to do something. For example, may he post a message? May he use a surcharged service? It is important to realize that authentication and authorization are distinct processesxe2x80x94one related to proving an identity and the other related to the properties of an identity. The present invention is not related to authorization, but it is designed to co-exist with authorization mechanisms.
Pass-phrase
A service that wishes to authenticate a user requires the user to identify himself or herself and to prove that he or she knows the pass-phrase. Generally, the service prompts the user for the pass-phrase. However, transmitting the plain text pass-phrases through a network comprises security because an eavesdropper may learn the pass-phrase as it travels through the network. X.25 networks have been compromised, and LANs, modem pools, and xe2x80x9cThe Internetxe2x80x9d likewise are not suitable for plain text pass-phrases due to the eavesdropper problem. Prompting for the pass-phrase, while sufficient in the past, no longer works for extensive world-wide networks.
Pass-phrase Encryption
Encryption of the pass-phrase provides additional security and addresses the eavesdropper problem. Using encryption, the user encrypts the pass-phrase, sends the result to the service which then decrypts it. Some techniques are based on a one-time key that prevents an eavesdropper from decrypting the pass-phrase.
There are, however, problems with this technique as well. Somebody elsexe2x80x94a spooferxe2x80x94may pretend to be the service. The spoofer decrypts the result, learns the pass-phrase, and gains the ability to masquerade as the user. Some people have spoofed services by getting users to dial into the spoofer""s computer. The spoofer advertises a dial up number for the service that is claimed to have been omitted from the directory of service numbers. The spoofer may entice people to try the xe2x80x9cunlistedxe2x80x9d number by claiming it is much faster than the listed numbers. Therefore, there is a need for a mechanism that will not reveal the pass-phrase to anyone, even if the user is interacting with a spoofer.
Challenge-response Techniques
Challenge-response techniques involve a series of exchanges between a user and a service. The service sends the user a challenge, which is a random number, and the user applies a one-way function to the number to calculate a result that depends on the challenge and the user""s pass-phrase. The user sends the result to the service which performs the same calculation and compares the result to the result sent by the user. Done correctly, this technique reveals no information to eavesdroppers, nor does it allow a spoofer to acquire the pass-phrasexe2x80x94if a spoofer pretends to be the service, he learns the result only for a particular challengexe2x80x94which is of no value. Although such a technique works, it does not solve the problem completely. The service must know the pass-phrase in order to reproduce the user""s calculation and verify the user""s response to the service""s challenge.
The service may not know the user""s pass-phrase for several reasons. A set of services may share a set of users"" identities. For example, a collection of Web servers, scattered throughout the world, may be part of a xe2x80x9cTotal Information Service (TIS).xe2x80x9d A user requesting access to TIS may use her TIS user name and pass-phrase to identify herself to any TIS service. In accordance with one implementation, each physical server may have a copy of all pass-phrases or access to a master database containing all pass-phrases. This solution may not, however, work under all scenariosxe2x80x94especially if some are third-party servers, not directly under the control of the imaginary TIS. Or consider a service that accepts identities in multiple realmsxe2x80x94for example, a service that has agreements with both CIS and AOL. The service gives the user a choice of realmsxe2x80x94xe2x80x9cPlease supply a CIS or AOL identity, and prove itxe2x80x9dxe2x80x94and the user chooses a realm in which he has an identity. It is unlikely that CIS and AOL will entrust a copy of their pass-phrase databases to a third-party service, or to each other. If the service does not know the user""s pass-phrase, then the user cannot prove to the service that he knows it.
One technique to address this problem is to have the service prompt the user for her pass-phase. For example, a WWW service may display a Hyper-Text Markup Language (HTML) form with two boxesxe2x80x94one that asks for the user for her user name and one that asks her for her pass-phrase. A protocol such as SSL or SHTTP may be used so an eavesdropper cannot see it. When the service receives the user""s reply, the service may use a challenge-response technique to verify the pass-phrase with a server that knows the pass-phrases. But, there is a drawback to this technique. It is important to teach a user not to type his or her pass-phrase just because somebody asks for it. This technique is commonly used for cracking others"" accounts. Teaching users to provide their pass-phrases in a HTML form is not a desirable solution because the pass-phrase is revealed, which is precisely what should be avoided, especially if the service is a spoofer.
The pass-phrase database server also has some undesirable side effects. Using this scheme, the service asks the user for a copy of her pass-phrase. Now, an ordinary challenge-response technique may be used. However, there is a need to get the pass-phrase from that database to the service, safely. If the service can look up the pass-phrase, then anybody else may do the same. Even worse, the entire pass-phrase database may be accessed so that pass-phrases for many users may be obtained.
Current authentication mechanisms are inadequate for the distributed systems, services, and users that comprise today""s world-wide networks such as the WWW/Internet. Users and services need a way to reliably authenticate one another that also meets specific design criteria. Users and services also have a need for a mechanism that is adaptable to the many communication protocols used throughout world-wide networks and that is straightforward for users to use. These criteria and others are met with the present invention.
The present inventionxe2x80x94Remote Passphrase Authentication (RPA)xe2x80x94provides a way to authenticate a user to a service by using a pass-phrase over an insecure network, without revealing the pass-phrase to eavesdroppers. RPA is designed so that the service need not know and does not learn the user""s pass-phrase. Consequently, RPA is useful in distributed environments where it would be difficult or inappropriate to trust a service with a pass-phrase database or to allow the service to learn enough to masquerade as the user in a future authentication attempt. In one embodiment of the present invention, users and services on the WWW/Internet use the mechanism of the present invention to authenticate one another.
Using the present invention, a service may authenticate a user and a user may authenticate a service. Authentication is accomplished using pass-phrases (which may be derived from textual phrases). The goal is to prove to the service that the user knows the pass-phrase, and vice versa. Techniques are employed to minimize the possibility that the pass-phrase is revealed to an eavesdropper or a spoofer.
Using RPA, a xe2x80x9cuserxe2x80x9d communicates with a xe2x80x9cservicexe2x80x9d that wishes to learn and authenticate the user""s identity. An authentication xe2x80x9cdeityxe2x80x9d knows the users"" and services"" pass-phrases. The service communicates with the authentication deity during the authentication process. If the service knows the pass-phrases, then it acts as its own deity, simplifying the implementation but, otherwise having no effect on the mechanism.
Identities for users exist in a xe2x80x9crealmxe2x80x9d which may be viewed as a relatively large collection of usersxe2x80x94such as compuserve.com or aol.comxe2x80x94but it may well consist of a small set of users (e.g., user names and pass-phrases associated with an individual Web server.) The service may specify a set of realms so that it may recognize an identity in any of the realms in which it participates.
This authentication mechanism of the present invention consists of three related processes: authentication, reauthentication, and reauthentication cheating. Authentication is the fundamental process by which a user and a service mutually authenticate one another within one of a set of realms, without revealing their pass-phrases to one another. Reauthentication is a process by which a user and service, having recently authenticated one another, may again authenticate one another. They may, of course, simply repeat the authentication process, but that requires interaction with an authentication deity. The reauthentication process is faster, requiring no communication with a third party. Reauthentication is useful when multiple connections between the user and service are established, whether sequential as in Hyper-Text Transfer Protocol (HTTP) or simultaneous. Preferably, each connection is authenticated, but the reauthentication process provides a shortcut.
Authentication
Three parties or entities participate in the authentication process:
the user;
the service; and
the authentication deity.
Each user has a user name and a pass-phrase in some realm of interest. Similarly, each service has a name and a pass-phrase in that realm. The pass-phrase is not text, but is instead a 128-bit (16-octet) string of bits. However, it is often useful to use pass-phrases in the conventional, textual sense, so a procedure is defined for converting a textual phrase to the 128-bit value used by the authentication mechanism of the present invention.
The service may specify a list of realms and the user may choose one in which he has an identity. For example, a CIS user may choose to be authenticated in the CIS realm. Thus, a service is not restricted to authenticating identities in a single realm. The service possesses a name and pass-phrase in all realms it specifies.
Each realm has an authentication deity that knows the names and pass-phrases of its members. The service locates an authentication deity for each realm. If the service knows the user""s pass-phrase, it performs the role of the authentication deity itself, but this does not affect the mechanism. The primary steps for a preferred embodiment of the present invention are as follows:
The service supplies a sequence of realms, with the service""s name in each realm, to the user.
The user chooses a realm. The chosen realm and the user""s name in that realm are communicated to the service.
The service and user exchange random challenges.
The user calculates a response and sends it to the service.
The service calculates a response.
The service sends a request to the authentication deity for the realm in question. The request contains the realm name, the user""s name, the service""s name, the user""s challenge, the service""s challenge, the user""s response, and the service""s response.
The deity uses the realm, service, and user name to look up the user""s and service""s pass-phrases.
The deity uses the values in the request, plus the service""s pass-phrase to verify the service""s response.
Having verified the requesting service""s identity, the deity uses the values in the request, plus the user""s pass-phrase to verify the user""s response.
Having verified both the user""s and service""s identity, the deity creates a random, 128-bit session key for use by the user and service. They may use it for session encryption or for the reauthentication process described later.
The authentication deity generates and sends to the service authentication proofs for the service and the user. The service verifies its authentication proof and forwards the other authentication proof to the user. The user then verifies its authentication proof.